package com.kavinz.algo.stack;

import com.kavinz.algo.queue.LinkedListQueue;

/**
 * <Cracking the coding interview> Exercise 3.1 Describe how you could use a
 * single array to implement three stacks <br>
 * Note:this implementation utilizes an extra auxiliary free list to address the
 * problem of not being able to reuse the newly freed spaces in the array.
 * 
 * @author Kevin Zhao
 * 
 */
public class TripleStackinOneArray<E> {

	// size of each stack
	int STACK_SIZE = 100;
	// an array that holds three stacks
	StackNode[] storage = new TripleStackinOneArray.StackNode[STACK_SIZE * 3];
	// the array index pointing to the top of each one of the three stacks
	int stackTopPt[] = new int[] { -1, -1, -1 };
	// the free space pointer queue
	LinkedListQueue<Integer> freeQueue = new LinkedListQueue<Integer>();

	class StackNode {
		StackNode pre;
		StackNode next;
		int index;// where this node is located in the array
		E item;
	}

	/**
	 * Linearly Looking for free slot in the array to put the newly added
	 * element<br>
	 * Ideally this method will not be used frequently,because in most cases
	 * freeQueue will be used instead to get a free slot in the array
	 * 
	 * @return
	 */
	private int linearProbing(int startOffset) {
		int result = startOffset + 1;
		while (storage[result] != null)
			result++;
		return result;
	}

	public void push(int stackNum, E value) {
		if (stackNum < 0 || stackNum > 2)
			throw new IndexOutOfBoundsException();
		int stackTop = stackTopPt[stackNum];

		int freeSlotIndex = -1;
		// 1.1 check the free queue for free slot
		try {
			freeSlotIndex = freeQueue.dequeue();
		} catch (IndexOutOfBoundsException e) {
			// this exception happens when the queue is empty
		}
		// 1.2 linearly looking for free slot
		if (freeSlotIndex == -1)
			freeSlotIndex = linearProbing(stackTopPt[stackNum]);
		// 2. update the stack top pointer
		stackTopPt[stackNum] = freeSlotIndex;
		// 3. find pre node
		StackNode preNode = null;
		if (stackTop != -1)
			preNode = storage[stackTop];
		// 4. link
		StackNode newNode = new StackNode();
		newNode.item = value;
		newNode.index = freeSlotIndex;
		newNode.pre = preNode;
		// 5. insertion
		storage[freeSlotIndex] = newNode;
	}

	public E pop(int stackNum) {
		if (stackNum < 0 || stackNum > 2)
			throw new IndexOutOfBoundsException();
		int stackTop = stackTopPt[stackNum];
		// empty stack
		if (stackTop == -1)
			return null;
		// get the node to be popped out
		StackNode poppedOutNode = storage[stackTop];
		StackNode pre = poppedOutNode.pre;

		// update the free queue
		freeQueue.enqueue(poppedOutNode.index);

		// the node to be popped out is the only node left in this particular
		// stack
		if (pre == null) {
			// update the stack top index
			stackTopPt[stackNum] = -1;

		} else {
			// update the stack top index
			stackTopPt[stackNum] = pre.index;
			pre.next = null;
		}
		// delete the node from the array
		storage[poppedOutNode.index] = null;

		return poppedOutNode.item;
	}

	public static void main(String[] args) {
		TripleStackinOneArray<String> stack = new TripleStackinOneArray<String>();

		// stack.push(0, "a1");
		// stack.push(0, "b1");
		// stack.push(0, "c1");
		// stack.push(1, "a2");
		// stack.push(1, "b2");
		// stack.push(1, "c2");
		// stack.push(2, "a3");
		// stack.push(2, "b3");
		// stack.push(2, "c3");
		//
		// System.out.println("pop-1:" + stack.pop(0));
		// System.out.println("pop-1:" + stack.pop(0));
		// System.out.println("pop-1:" + stack.pop(0));
		//
		// System.out.println("pop-2:" + stack.pop(1));
		// System.out.println("pop-2:" + stack.pop(1));
		// System.out.println("pop-2:" + stack.pop(1));
		//
		// System.out.println("pop-3:" + stack.pop(2));
		// System.out.println("pop-3:" + stack.pop(2));
		// System.out.println("pop-3:" + stack.pop(2));

		stack.push(0, "a1");
		stack.push(0, "b1");
		stack.push(1, "a2");
		stack.push(1, "b2");
		stack.push(0, "c1");

		stack.pop(1);

		stack.push(0, "d1");

	}
}
